Randers được xây dựng từ khoảng thế kỷ 11, tuy nhiên cũng có các di tích từ thời đại Viking ở đây. Vua thánh Knud đã cho đúc tiền tại Randers khoảng năm 1080. Năm 1086 các người nổi dậy chống ông ta đã tập họp trong thành phố này.

Thời trung cổ, Randers được củng cố về mặt phòng thủ. Tuy ngày nay không tìm thấy dấu vết của bờ lũy bao quanh thành phố, nhưng qua các tên đường phố như Østervold (bờ lũy phía đông), Nørreport (cổng phía bắc), Vestervold (bờ lũy phía tây), Lille Voldgade (đường phố Bờ lũy nhỏ) vv..., 4 đường phố nằm vòng tròn, dường như đã cho biết vị trí thành phố thời xưa.

Randers bị xóa sổ 3 lần trong thế kỷ 13, trong đó năm 1246 bị quân của Abel thiêu rụi trong cuộc nội chiến với Erik 4. Plovpenning.

Năm 1302, thành phố được vua Erik Menved cấp cho đặc quyền thương trấn.

Ta có thể đi bộ trên 1 đường phố nội thành, xem ngôi nhà mà theo truyền thuyết, người anh hùng Niels Ebbesen năm 1340 đã giết tên bá tước hói đầu (tiếng Đan Mạch cổ "vog den kullede greve" = dræbte den skaldede greve). Bá tước bị giết ở đây là Gerhard, bá tước vùng Holstein, người đã nắm quyền kiểm soát phần lớn bán đảo Jutland trong thời kỳ Đam Mạch trống ngôi vua. Việc giết bá tước đó diễn ra ở tầng 3 của ngôi nhà. Người ta đã dựng tượng của Niels Ebbesen trước tòa thị chính thành phố.

Khi vua Valdemar Atterdag năm 1350 tìm cách tập hợp vương quốc, sau khi cầm cố cho bá tước vùng Holstein, thành phố Randers đã được củng cố bằng pháo đài và thường được gọi là Randershus. Pháo đài này bị các quý tộc bất mãn chiếm năm 1357. Năm 1359 Valdemar lại tấn công thành phố.

Năm 1534 các nông dân nổi dậy, do Skipper Clement lãnh đạo, họ tìm cách chiếm thành phố nhưng bị quân phòng thủ sau bờ lũy đẩy lui.

Dưới thời Christian 3 (1536-1559) các công sự phòng thủ với hào sâu, lũy cao được xây dựng chung quanh thành phố. Sau thời Cải cách (sang đạo Tin Lành), Christian 3 cho xây lại tu viện dòng thánh Phanxicô cũ thành nơi cư ngụ cho hoàng hậu. Tu viện sau đó được gọi là Lâu đài Hoàng hậu (Dronningborg Slot).